題目連結(https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
今天來談需要思考的應用題型,一維 DP(Dynamic Programming) 動態規劃經典題
prices ,prices[i] 表示第 i 天的買價第二天為買價最低,接下來的賣價第五天最高,因此最大利潤為第五天減第二天的價值=6-1=5。
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
特殊案例
Input: prices = [7,6,4,3,1]
Output: 0
Explanation:
- 價格持續下降
- 無法獲利,返回 0
minb 保存 目前最小買價
prices[i]:
prices[i] 視為賣價,計算利潤 prices[i] - minb
maxp = max(maxp, prices[i] - minb)
minb = min(minb, prices[i])
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxp = 0; //初始化最大利潤
int minb = prices[0]; //初始化最小買價
for(int i = 0; i < prices.size(); i++){
int sell = prices[i];
maxp = max(maxp, sell - minb); //確認利潤會不會比原先儲存的高
minb = min(minb, sell); //更新最小買價
}
return maxp;
}
};
prices = [7,6,4,3,1]
-> maxProfit = 0
prices = [1,2,3,4,5]
-> maxProfit = 4
maxProfit = dp[i]:到第 i 天為止最大利潤minBuy = dp 的狀態:歷史最小買價ps. 部分內容經 AI 協助整理